package com.hard;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * TODO(2127. 参加会议的最多员工数)
 * 第 274 场周赛
 *
 *  一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。
 *
 * 员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。
 *
 * 给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-employees-to-be-invited-to-a-meeting
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *
 * @author leon
 * @date 2022年01月03日 20:08
 */
public class MaximumInvitations {
    public int maximumInvitations(int[] favorite) {
        ArrayList<Integer>[] list = new ArrayList[favorite.length];
        for (int i = 0; i < favorite.length; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i = 0; i < favorite.length; i++) {
            list[favorite[i]].add(i);
        }
        int max = 0, visited[] = new int[favorite.length];
        for (int i = 0; i < favorite.length; i++) {
            max += i < favorite[i] || favorite[favorite[i]] != i ? 0
                    : maximumInvitations(i, favorite[i], list) + maximumInvitations(favorite[i], i, list);
        }
        for (int i = 0, j; (j = i) < favorite.length; i++) {
            if (visited[i] == 0) {
                HashMap<Integer, Integer> map = new HashMap<>();
                for (int k = 0; visited[j] == 0; visited[j] = 1, map.put(j, k++), j = favorite[j]) {
                }
                max = Math.max(max, map.size() - map.getOrDefault(j, map.size()));
            }
        }
        return max;
    }

    private int maximumInvitations(int i, int j, ArrayList<Integer>[] list) {
        int max = 0;
        for (int k : list[i]) {
            max = Math.max(max, k == j ? 0 : maximumInvitations(k, j, list));
        }
        return 1 + max;
    }
}
